package 每日一题;

import java.util.Arrays;

/**
 * 757. 设置交集大小至少为2
 * 一个整数区间 [a, b]  ( a < b ) 代表着从 a 到 b 的所有连续整数，包括 a 和 b。
 *
 * 给你一组整数区间intervals，请找到一个最小的集合 S，使得 S 里的元素与区间intervals中的每一个整数区间都至少有2个元素相交。
 *
 * 输出这个最小集合S的大小。
 *
 * 示例 1:
 *
 * 输入: intervals = [[1, 3], [1, 4], [2, 5], [3, 5]]
 * 输出: 3
 * 解释:
 * 考虑集合 S = {2, 3, 4}. S与intervals中的四个区间都有至少2个相交的元素。
 * 且这是S最小的情况，故我们输出3。
 * 示例 2:
 *
 * 输入: intervals = [[1, 2], [2, 3], [2, 4], [4, 5]]
 * 输出: 5
 * 解释:
 * 最小的集合S = {1, 2, 3, 4, 5}.
 * 注意:
 *
 * intervals 的长度范围为[1, 3000]。
 * intervals[i] 长度为 2，分别代表左、右边界。
 * intervals[i][j] 的值是 [0, 10^8]范围内的整数。
 */
public class D220722_T0757 {
    public int intersectionSizeTwo(int[][] intervals) {

        // 贪心算法  按照右端 从小到大进行排序
        //先排序，以右边界为关键字排序，右边界相同的，按左边界降序排序，先处理长度较小的区间
        Arrays.sort(intervals, (o1, o2) -> {
            if (o2[1] != o1[1]) {
                return o1[1] - o2[1];
            }
            if (o2[0] != o1[0]) {
                return o2[0] - o1[0];
            }
            return 0;
        });

//        HashSet<Integer> hashSet = new HashSet<>(); //集合S的值
        int count = 2;
        //将第一个区间 的最后两个元素 记录下来
        int elementMax = intervals[0][intervals[0].length - 1];
        int elementMin = intervals[0][intervals[0].length - 1] - 1;

        for (int i = 1; i < intervals.length; i++) {
            int tempCount = 0; //记录本区间右几个与S 相交的元素

            // 当前区间 与上一个区间 有交集 且大于等于2
            if (intervals[i][0] <= elementMin) {
                continue;
            }
            // 当前区间 与上一个区间 有交集 但是只有一个 //更新最后两个元素
            if (intervals[i][0] <= elementMax) {
                elementMin = elementMax;
                elementMax = intervals[i][intervals[i].length - 1];
                count++;
                continue;
            }

            //当前区间与上一个区间没有交集
            if (intervals[i][0] > elementMax) {
                count += 2;
                elementMax = intervals[i][intervals[i].length - 1];
                elementMin = intervals[i][intervals[i].length - 1] - 1;
            }


        }

        return count;

    }

    public static void main(String[] args) {
        D220722_T0757 d220722_t0757 = new D220722_T0757();
        d220722_t0757.intersectionSizeTwo(new int[][]{{1, 3}, {3, 7}, {5, 7}, {7, 8}});
    }
}